<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="./dict.js"></script>
  <title>图结构</title>
</head>

<body>
  <script>
    // 封装队列类
    function Queue() {
      // 属性
      this.items = []
      // 方法
      // 1.将元素加入到队列
      Queue.prototype.enqueue = function (element) {
        this.items.push(element)
      }
      // 2.从队列中删除前端元素
      Queue.prototype.dequeue = function () {
        return this.items.shift()
      }
      // 3.查看前端的元素
      Queue.prototype.front = function () {
        return this.items[0]
      }
      // 4.查看队列是否为空
      Queue.prototype.isEmpty = function () {
        return this.items.length == 0
      }
      // 5.查看队列中元素的个数
      Queue.prototype.size = function () {
        return this.items.length
      }
      // 6.toString方法
      Queue.prototype.toString = function () {
        let string = ''
        for (let i = 0; i < this.items.length; i++) {
          string += this.items[i] + '--'
        }
        return string
      }
    }
    // 封装图类
    function Graph() {
      // 属性:顶点 (数组) / 边(字典)
      this.vertexes = [] // 顶点
      this.edges = new Dictionary() //边

      // 方法
      // 添加顶点
      Graph.prototype.addVertex = function (v) {
        this.vertexes.push(v)
        this.edges.set(v, [])
      }
      // 添加边
      Graph.prototype.addEdge = function (v1, v2) {
        this.edges.get(v1).push(v2)
        this.edges.get(v2).push(v1)
      }
      // toString
      Graph.prototype.toString = function () {
        //定义字符串,保存最终结果
        var resultString = ''
        // 遍历所有的顶点,以及顶点对应的边
        for (let i = 0; i < this.vertexes.length; i++) {
          resultString += this.vertexes[i] + '->'
          var vEdges = this.edges.get(this.vertexes[i])
          for (let i = 0; i < vEdges.length; i++) {
            resultString += vEdges[i] + ''
          }
          resultString += '\n'
        }
        return resultString
      }
      // 初始化状态颜色
      Graph.prototype.initializeColor = function () {
        var colors = []
        for (var i = 0; i < this.vertexes.length; i++) {
          colors[this.vertexes[i]] = 'white'
        }
        return colors
      }
      // 实现广度优先搜索(BFS)
      Graph.prototype.bfs = function (initV, handler) {
        // 1.初始化颜色
        var colors = this.initializeColor()
        // 2.创建队列
        var queue = new Queue()
        // 3.将顶点加入到队列
        queue.enqueue(initV)
       
        // 4.循环从队列取出元素
        while (!queue.isEmpty()) {
          // 从队列取出一个顶点
          var v = queue.dequeue()
          // 获取和顶点相连的另外两个顶点
          var vList = this.edges.get(v)
          // 将v的颜色设置成灰色
          colors[v] = 'gray'
          // // 遍历所有顶点 并且加入到队列中
          for (var i = 0; i < vList.length; i++) {
            var e = vList[i]
            if (colors[e] == 'white') {
              colors[e] = 'gray'
              queue.enqueue(e)
            }
          }
          // 访问顶点
          handler(v)
          // 将顶点设置为黑色
          colors[v] = 'black'
        }
      }
    }



    // 测试代码
    // 创建图结构
    var g = new Graph()

    // 添加顶点
    var myVertexes = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
    for (var i = 0; i < myVertexes.length; i++) {
      g.addVertex(myVertexes[i])
    }

    // 添加边
    g.addEdge('a', 'b')
    g.addEdge('a', 'c')
    g.addEdge('a', 'd')
    g.addEdge('c', 'd')
    g.addEdge('c', 'g')
    g.addEdge('d', 'g')
    g.addEdge('d', 'h')
    g.addEdge('b', 'e')
    g.addEdge('b', 'f')
    g.addEdge('e', 'i')

    // 测试结果
    alert(g);
    // 测试dfs
    var result = ''
    g.bfs(g.vertexes[0], function (v) {
      result += v + ' '
    })
   
    alert(result);

  </script>
</body>

</html>